package leecode;

import org.junit.Test;

public class _35 {
    public int searchInsert(int[] nums, int target) {
        return binarySearch(0, nums.length-1, nums, target);
    }

    public int binarySearch(int low , int high , int[] nums , int target) {
        if (low <= high){
            if (low == high){
                if (target <= nums[low])
                    return low;
                return low + 1;
            }
            int mid = (low + high ) / 2;
            if (nums[mid] > target) {
                return binarySearch(low , mid-1 , nums , target);
            }
            else if (nums[mid] < target)
                return binarySearch(mid+1 , high , nums ,target);
            else return mid;
        }
        return low;
    }

    @Test
    public void test () {
        int[] nums = new int[] {3,5,7,9,10};
        int i = searchInsert(nums, 8);
        System.out.println(i);
    }
}
